<!DOCTYPE html>
<html>
  <head>
    <title>Numεrωmikωn</title>
    <link rel="stylesheet" href="../stock.css">
    <link rel="icon" type="image/x-icon" href="../favicon.ico">
    <meta content="text/html;charset=utf-8" http-equiv="Content-Type"/>
    <meta name="viewport" content="width=device-width, initial-scale=1" />
  </head>

  <body>
    <div class ="nav">
      <a href="../index">Indεχ</a>
      <a href="../clanky">Článκy</a>
      <a class="active" href="../googologie">Gωωgωlωgiε</a>
      <a href="../o_mne">Ω mně</a>
    </div>

    <div class="content-googology">
      <h1>Hardyho hierarchie ~ <i>f<sub>ω<sup>ω</sup></sub>(n)</i></h1>

      <p>Podívejme se na pravidla Hardyho hierarchie:</p>

      <div class="math"> 
        <p>h<sub>0</sub>(n) = n</p>
        <p>h<sub>α	+ 1</sub>(n) = h<sub>α</sub>(n + 1)</p>
        <p>h<sub>β</sub>(n) = h<sub>β[n]</sub>(n), je-li β mezní ordinál</p> 
      </div>

      <p>------</p>

      <p>Na první pohled vidíme zásadní rozdíly; nultá funkce pouze vypíše vstup a při přecházení na nižší ordinály neopakujeme funkci
      nkrát. Pro malé ordinály to bude vypadat, že funkce z této hierarchie budou slabé, ale věz, že je to klam.</p>

      <p>Zkusme si příklad s konečným ordinálem:</p>

      <div class="math"> 
        <p>h<sub>4</sub>(100) = h<sub>3</sub>(101)</p>
        <p>h<sub>3</sub>(101) = h<sub>2</sub>(102)</p>
        <p>h<sub>2</sub>(102) = h<sub>1</sub>(103)</p>
        <p>h<sub>1</sub>(103) = h<sub>0</sub>(104)</p>
        <p>h<sub>0</sub>(104) = 104</p>
      </div>

      <p>------</p>

      <p>Proč tolik povyku, abychom ze <i>100</i> dostali <i>104</i>? Kdybychom použili rychle rostoucí hierarchii, již bychom měli číslo větší než
      <i>2 ↑↑↑ 100</i>. Zkusme si další příklad, tentokrát s nekonečným ordinálem:</p>

      <div class="math"> 
        <p>h<sub>ω</sub>(100) = h<sub>100</sub>(100)</p>
        <p>...</p>
        <p>h<sub>0</sub>(200) = 200</p>
      </div>

      <p>------</p>

      <p>Nic moc teda! <i>ω</i> nabízí jenom násobení dvěma. Co nám to ale připomíná?</p>

      <div class="math"> 
        <p>h<sub>ω</sub>(n) = f<sub>1</sub>(n)</p>
      </div>

      <p>------</p>

      <p>Zajímavé. Z mocné <i>ω</i> se stala první rychle rostoucí funkce. Možná to potřebuje víc šťávy:</p>

      <div class="math">
        <p>h<sub>ω + 2</sub>(100) = h<sub>ω + 1</sub>(101)</p>
        <p>h<sub>ω + 1</sub>(101) = h<sub>ω</sub>(102)</p>
      </div>

      <p>To už nemusíme dopočítávat. Takže <i>x</i> v <i>ω + x</i> pouze výsledku přidá 2x svoji hodnotu? U rychle rostoucí hierarchie
      jsme kvůli tomu museli opakovat Grahamovu funkci! No nic, zkusme mnohem větší ordinály:</p>

      <div class="math"> 
        <p>h<sub>ω<sup>ω</sup></sub>(100) = h<sub>ω<sup>100</sup></sub>(100)</p>
        <p>h<sub>ω<sup>100</sup></sub>(100) = h<sub>ω<sup>99</sup> * 100</sub>(100)</p>
        <p>h<sub>ω<sup>99</sup> * 100</sub>(100) = h<sub>ω<sup>99</sup> * 99 + ω<sup>98</sup> * 100</sub>(100)</p>
      </div>

      <p>Počkat! To bychom se asi nikdy nedopočítali! Zkusme menší vstup:</p>

      <div class="math">
        <p>h<sub>ω<sup>ω</sup></sub>(3) = h<sub>ω<sup>3</sup></sub>(3)</p>
        <p>h<sub>ω<sup>3</sup></sub>(3) = h<sub>ω<sup>2</sup> * 3</sub>(3)</p>
        <p>h<sub>ω<sup>2</sup> * 3</sub>(3) = h<sub>ω<sup>2</sup> * 2 + ω * 3</sub></p>
      </div>

      <p>Hmm, to by taky trvalo dlouho. Dvojku snad zvládneme:</p>

      <div class="math"> 
        <p>h<sub>ω<sup>ω</sup></sub>(2) = h<sub>ω<sup>2</sup></sub>(2)</p>
        <p>h<sub>ω<sup>2</sup></sub>(2) = h<sub>ω * 2</sub>(2)</p>
        <p>h<sub>ω * 2</sub>(2) = h<sub>ω + 2</sub>(2)</p>
      </div>

      <p>To nám je povědomé! Přece <i>ω + x</i> zdvojnásobí vstup a přidá výsledku <i>2 * x</i>. Tudíž:</p>

      <div class="math"> 
        <p>h<sub>ω<sup>ω</sup></sub>(2) = 8</p>
      </div>

      <p>------</p>

      <p>To bylo hodně rozepisování ordinálů! Co nám připomíná výsledek <i>h<sub>ω<sup>ω</sup></sub>(2)</i>?
      Vždyť to je výsledek z <i>f<sub>2</sub>(2)</i>, nebo ne? To by bylo <i>2<sup>2</sup> * 2</i>; to je <i>8</i>.
      Víš, co to znamená? Hleď:</p>

      <div class="math"> 
        <p>h<sub>ω<sup>ω</sup></sub>(2) = f<sub>2</sub>(2)</p>
        <p>h<sub>ω<sup>ω</sup></sub>(3) = f<sub>3</sub>(3)</p>
        <p>h<sub>ω<sup>ω</sup></sub>(100) = f<sub>100</sub>(100)</p>
      </div>

      <p>------</p>

      <p>Jaké to štěstí, že jsme nedopočítali <i>h<sub>ω<sup>ω</sup></sub>(100)</i> ani obdobu s trojkou! S trojkou bychom se tu prali
      poměrně dlouho, ale se stovkou bychom tu byli do konce vesmíru a nikam bychom nepokročili! Z toho plyne:</p>

      <div class="math">
        <p>h<sub>ω<sup>ω</sup></sub>(n) = f<sub>n</sub>(n)</p>
        <p>f<sub>n</sub>(n) = f<sub>ω</sub>(n)</p>
      </div>

      <p>------</p>

      <p>Hardyho hierarchie je tedy jen o pouhý krok pozadu! Celkově platí:</p>

      <div class="math"> 
        <p>h<sub>ω ↑↑ x</sub>(n) = f<sub>ω ↑↑ (x - 1)</sub>(n)</p>
      </div>

      <p>------</p>

      <p>Opravdu jsme i viděli, že <i>h<sub>ω</sub>(n) = f<sub>1</sub>(n)</i>, protože <i>ω ↑↑ 0</i> je vskutku <i>1</i>. Kdybychom dosadili třeba ordinál
      <i>ω<sup>ω<sup>ω</sup></sup></sup></i> do indexu Hardyho hierarchie, vytvořili bychom pořádnou továrnu na velká čísla:</p>

      <div class="math"> 
        <p>h<sub>ω<sup>ω<sup>ω</sup></sup></sub>(5) = h<sub>ω<sup>ω<sup>5</sup></sup></sub>(5)</p>
      </div>

      <p>Abychom viděli, jak postupují ordinály s <i>n</i> rovno pěti, zapíšeme je samotné popořadě:</p>

      <div class="math"> 
        <p>ω<sup>ω<sup>5</sup></sup> = ω<sup>ω<sup>4</sup> * 5</sup></p>
        <p>ω<sup>ω<sup>4</sup> * 5</sup> = ω<sup>ω<sup>4</sup> * 4 + ω<sup>3</sup> * 5</sup></p>
        <p>...</p>
        <p>ω<sup>ω<sup>5</sup></sup> = ω<sup>ω<sup>4</sup> * 4 + ω<sup>3</sup> * 4 + ω<sup>2</sup> * 4 + ω * 4 + 5</sup></p>
      </div>

      <p>------</p>

      <p>Nikdy bychom nevypsali celou řadu ani na papír velký několik miliard galaxií.</p>

      <p>Procvičili jsme si práci s nekonečnými ordinály a viděli, jak i velmi slabě vypadající hierarchie funkcí může splodit nepředstavitelně
      ohromná čísla, užijeme-li velkých ordinálů. Navíc Hardyho hierarchie pro nás bude užitečná, až se setkáme s Goodsteinovým teorémem.</p>
    </div>

    <footer>
      <p class="footer"><a class="silent" href="https://creativecommons.org/licenses/by/4.0/" target="_blank">Kristian Tichota (CC-BY-4.0)</a></p>
    </footer>
  </body>
</html>
